// d[i][i]=1
// dp[i][j] = dp[i+1][j-1]+2 当s[i]=s[j]
// dp[i][j]=max(dp[i+1][j],dp[i][j-1])
//  当s[i]!=s[j] 取s[i+1..j] 和s[i..j-1]中最长的
//  由于dp[i][j]需要dp[i+1][j]所以需要逆序枚举s的长度，而又因为j是递增的，
//  所以在求解dp[i][j]时,dp[i][j-1]肯定已经求解过了


/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    let l = s.length;
    if (l <= 1) {
        return l;
    }

    // 初始化一个 dp[l][l]
    let dp = new Array(l);
    for (let i = 0; i < l; i++) {
        dp[i] = new Array(l);
        dp[i].fill(0, 0, l)
        dp[i][i] = 1
    }
    console.log(dp)

    // 从右下角开始，逐渐往上推
    for (let i = l - 2; i >= 0; i--) {
        for (let j = i + 1; j <= l - 1; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(
                    dp[i + 1][j],
                    dp[i][j - 1]
                )
            }
        }
    }
    console.log(dp)
    return dp[0][l - 1]
};


console.log(longestPalindromeSubseq("bbaab"))
